package My_Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 周斌
 * Date: 2024-03-11
 * Time: 20:27
 */
public class LinkedStack {
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;
    //push 用头插法和尾插法都行，时间复杂度都为O(1)
    //1.头插法
    public void push1(int val) {
        ListNode node = new ListNode(val);
        if(head == null) {
            head = node;
            last = node;
        }
        else {
            node.next = head;
            head.prev =node;
            head= node;
        }
    }
    //2.尾插法
    public void push2(int val) {
        ListNode node = new ListNode(val);
        if(head == null) {
            head = node;
            last = node;
        }
        else {
            node.prev = last;
            last.next =node;
            last = node;
        }
    }
    //pop 出栈 1.采用头插法，直接删头节点 2.采用尾插法，直接删尾节点
    //1.删头节点
    public int pop1() {
        ListNode cur = head.next;
        int ret = head.val;
        head = cur;
        return ret;
    }
    //2.删尾节点
    public int pop2() {
        ListNode cur = last.prev;
        int ret = last.val;
        last = cur;
        return ret;
    }
    //peek 1.采用头插法，直接返回head的值 2.采用尾插法，直接返回last的值
    public int peek1() {
        return head.val;
    }
    public int peek2() {
        return last.val;
    }
}
